Section: Scientific Foundations

Compilation of Signal

Sequential code generation starting from a Signal specification starts with an analysis of its implicit synchronization and scheduling relations. This analysis yields the control and data-flow graphs that define the class of sequentially executable specifications and allow to generate code.

Synchronization and scheduling specifications

In Signal, the clock $\widehat{}x$ of a signal $x$ denotes the set of instants at which the signal $x$ is present. It is represented by a signal that is true when $x$ is present and that is absent otherwise. Clock expressions represent control. The clock $\mathrm{𝚠𝚑𝚎𝚗}x$ (resp. $\mathrm{𝚠𝚑𝚎𝚗}\mathrm{𝚗𝚘𝚝}x$) represents the time tags at which a boolean signal $x$ is present and true (resp. false).

The empty clock is written $\widehat{}0$ and clock expressions $e$ combined using conjunction, disjunction and symmetric difference. Clock equations $E$ are Signal processes: the equation $e\widehat{}=e^{\text{'}}$ synchronizes the clocks $e$ and $e^{\text{'}}$ while $e\widehat{}<e^{\text{'}}$ specifies the containment of $e$ in $e^{\text{'}}$. Explicit scheduling relations $x\to y\mathrm{𝚠𝚑𝚎𝚗}e$ allow to schedule the calculation of signals (e.g. $x$ after $y$ at the clock $e$).

Synchronization and scheduling analysis

A Signal process $P$ corresponds to a system of clock and scheduling relations $E$ that denotes its timing structure. It can be defined by induction on the structure of $P$ using the inference system $P:E$ of Figure 5 .

    x := y$ init v   : ^x ^= ^y

    x := y when z    : ^x ^= ^y when z | y -> x when z

    x := y default z : ^x ^= ^y default ^z | y -> x when ^y | z -> x when ^z ^- ^y

Hierarchization

The clock and scheduling relations $E$ of a process $P$ define the control-flow and data-flow graphs that hold all necessary information to compile a Signal specification upon satisfaction of the property of endochrony. A process is said endochronous iff, given a set of input signals and flow-equivalent input behaviors, it has the capability to reconstruct a unique synchronous behavior up to clock-equivalence: the input and output signals are ordered in clock-equivalent ways.

Figure 6. Hierarchization of clocks

To determine the order $x⪯y$ in which signals are processed during the period of a reaction, clock relations $E$ play an essential role. The process of determining this order is called hierarchization and consists of an insertion algorithm which hooks elementary control flow graphs (in the form of if-then-else structures) one to the others. Figure 6 , right, let h3 be a clock computed using h1 and h2. Let h be the head of a tree from which h1 and h2 are computed (an if-then-else), h3 is computed after h1 and h2 and placed under h [28] .